#!/usr/bin/env python
# -*- coding: utf-8 -*-

from NFA import NFA
import networkx as nx
import matplotlib.pyplot as plt

class DFA:

    def __init__(self, NFA):
        self.name = ''
        stateStack = []
        tempStateStack = []
        self.originMap = NFA.transferTable
        self.transferTable = []
        initState = self.Eclosure()
        tempStateStack.append(initState)
        DFAhead = list(set(self.originMap[0]).difference(set(['ε'])))
        headIndex = DFAhead.index('head')
        if headIndex != 0:
            DFAhead[headIndex] = DFAhead[0]
            DFAhead[0] = 'head'
        self.transferTable += [DFAhead]
        while len(tempStateStack) != 0:
            line = [[] for i in range(len(DFAhead))]
            State = tempStateStack.pop()
            state = State[:]
            stateStack += [State]
            line[0] = State
            for value in DFAhead:
                if value != 'head':
                    valueIndx = DFAhead.index(value)
                    isInStack = False
                    isIntemp = False
                    tempState = self.Vclosure(state, value)
                    tempStateCopy = tempState[:]
                    line[valueIndx] = tempState
                    for resultState in stateStack:
                        resultStateCopy = resultState[:]
                        if list(set(resultStateCopy).difference(set(tempStateCopy))) == list(set(tempStateCopy).difference(set(resultStateCopy))) == []:
                            isInStack = True
                            break
                    for midState in tempStateStack:
                        midStateCopy = midState[:]
                        if list(set(midStateCopy).difference(set(tempStateCopy))) == list(set(tempStateCopy).difference(set(midStateCopy))) == []:
                            isIntemp = True
                            break
                    if not isInStack and not isIntemp and tempState != []:
                        tempStateStack.append(tempState)
            lineCopy = line[:]
            self.transferTable += [lineCopy]
        self.states = stateStack
        self.order = []
        self.endStates = []
        for i in range(len(self.states)):
            if 100 in self.states[i]:
                self.endStates += [i]
            self.order += [i]
        for i in range(1, len(self.transferTable)):
            for j in range(len(self.transferTable[i])):
                value = self.transferTable[i][j]
                for compState in self.states:
                    compStateCopy = compState[:]
                    if list(set(value).difference(set(compStateCopy))) == list(set(compStateCopy).difference(set(value))) == []:
                        exchange = self.order[self.states.index(compState)]
                        self.transferTable[i][j] = exchange
                        break

    def Eclosure(self):
        index = len(self.originMap[0])-1
        result = []
        temp = []
        tempRecorder = []
        temp.append(0)
        while len(temp) != 0:
            state = temp.pop()
            result.append(state)
            tempRecorder.append(state)
            if state == 100:
                state = len(self.originMap) - 2
            if self.originMap[state+1][index] == '∅':
                continue
            else:
                for value in self.originMap[state+1][index]:
                    if value not in tempRecorder and value not in temp:
                        temp.append(value)
        return result

    def Vclosure(self, stateSet, mark):
        index = self.originMap[0].index(mark)
        eIndex = len(self.originMap[0])-1
        result = []
        PE = stateSet[:]
        BE = []
        PERecorder = []
        BERecorder = []
        V = []
        VRecorder = []
        while len(PE) != 0:
            state = PE.pop()
            PERecorder.append(state)
            if state == 100:
                state = len(self.originMap) - 2
            if self.originMap[state+1][eIndex] == '∅' and self.originMap[state+1][index] == '∅':
                continue
            if self.originMap[state+1][eIndex] != '∅':
                for value in self.originMap[state+1][eIndex]:
                    if value not in PE and value not in PERecorder:
                        PE.append(value)
            if self.originMap[state+1][index] != '∅':
                for value in self.originMap[state+1][index]:
                    if value not in V and value not in VRecorder:
                        V.append(value)
        while len(V) != 0:
            state = V.pop()
            result.append(state)
            VRecorder.append(state)
            if state == 100:
                state = len(self.originMap) - 2
            if self.originMap[state+1][eIndex] == '∅' and self.originMap[state+1][index] == '∅':
                continue
            if self.originMap[state+1][eIndex] != '∅':
                for value in self.originMap[state+1][eIndex]:
                    if value not in BE and value not in BERecorder:
                        BE.append(value)
            if self.originMap[state+1][index] != '∅':
                for value in self.originMap[state+1][index]:
                    if value not in V and value not in VRecorder:
                        V.append(value)
        while len(BE) != 0:
            state = BE.pop()
            result.append(state)
            BERecorder.append(state)
            if state == 100:
                state = len(self.originMap) - 2
            if self.originMap[state+1][eIndex] == '∅':
                continue
            else:
                for value in self.originMap[state+1][eIndex]:
                    if value not in BE and value not in BERecorder:
                        BE.append(value)
        return result

    def isTransCondition(self, Input):
        asc = ord(Input)
        if '/w' in self.transferTable[0]:
            if (asc > 64 and asc < 91) or (asc > 96 and asc < 123) or asc == 95:
                Input = '/w'
        if '/d' in self.transferTable[0]:
            if asc > 47 and asc < 58:
                Input = '/d'
        if '/e' in self.transferTable[0]:
            if Input != '*' and Input != '/':
                Input = '/e'
        if '/l' in self.transferTable[0]:
            if Input == '/':
                Input = '/l'
        if '/x' in self.transferTable[0]:
            if Input == '*':
                Input = '/x'
        if '/o' in self.transferTable[0]:
            if Input == '|':
                Input = '/o'
        if '/a' in self.transferTable[0]:
            if Input == '&':
                Input = '/a'
        if '//' in self.transferTable[0]:
            if Input == '/':
                Input = '//'
        if '/h' in self.transferTable[0]:
            if Input in [ '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F' ]:
                Input = '/h'
        if Input in self.transferTable[0]:
            return True
        else:
            return False

    def trans(self, Input, currentState):
        asc = ord(Input)
        if '/w' in self.transferTable[0]:
            if (asc > 64 and asc < 91) or (asc > 96 and asc < 123) or asc == 95:
                Input = '/w'
        if '/d' in self.transferTable[0]:
            if asc > 47 and asc < 58:
                Input = '/d'
        if '/e' in self.transferTable[0]:
            if Input != '*' and Input != '/':
                Input = '/e'
        if '/l' in self.transferTable[0]:
            if Input == '/':
                Input = '/l'
        if '/x' in self.transferTable[0]:
            if Input == '*':
                Input = '/x'
        if '/o' in self.transferTable[0]:
            if Input == '|':
                Input = '/o'
        if '/a' in self.transferTable[0]:
            if Input == '&':
                Input = '/a'
        if '//' in self.transferTable[0]:
            if Input == '/':
                Input = '//'
        if '/h' in self.transferTable[0]:
            if Input in [ '1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F' ]:
                Input = '/h'
        if Input in self.transferTable[0]:
            # print Input
            index = self.transferTable[0].index(str(Input))
            # print index
            nextState = self.transferTable[int(str(currentState))+1][index]
            if nextState != []:
                return True, nextState
            else:
                return False, False
        else:
            return False, False


    def showTransferTable(self):
        for line in self.transferTable:
            content = ''
            for value in line:
                if value != []:
                    content += str(value) + '\t'
                else:
                    content += '∅' + '\t'
            print content

    def draw(self):
        labels = {}
        transMap = self.transferTable
        G = nx.MultiDiGraph()
        for i in range(len(self.states)):
            G.add_node(i)
            labels[i] = i
        for i in range(1, len(self.states)+1):
            for j in range(1, len(transMap[0])):
                if transMap[i][j] != []:
                    G.add_weighted_edges_from([(transMap[i][0], transMap[i][j], transMap[0][j])])
        pos=nx.graphviz_layout(G)
        edge_labels = nx.get_edge_attributes(G, 'weight')
        nx.draw_networkx_nodes(G, pos, node_color='r', node_size=500, alpha=0.8)
        nx.draw_networkx_nodes(G, pos, nodelist=[0], node_color='b', node_size=500, alpha=0.8)
        nx.draw_networkx_nodes(G, pos, nodelist=self.endStates, node_color='g', node_size=500, alpha=0.8)
        nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5, edge_color='b')
        nx.draw_networkx_labels(G, pos, labels, font_size=16)
        nx.draw_networkx_edge_labels(G, pos, edge_labels)
        plt.draw()
        plt.show()

if __name__ == "__main__":
    a = NFA("a", 0)
    b = NFA("b", 0)
    c = NFA("c", 0)
    One = NFA("1", 0)
    Two = NFA("2", 0)
    word = NFA("/w", 0)
    number = NFA("/d", 0)
    dot = NFA("/.", 0)
    # test1 = b.seriesConnection(b.circuitConnection())
    # test1.showTransferTable()
    # test1.fomalize()
    # test2 = word.parallelConnection(number).parallelConnection(a).seriesConnection(One).circuitConnection()
    # name = word.seriesConnection(word.parallelConnection(number).circuitConnection())
    # name.fomalize()
    # name.showTransferTable()
    Number = number.seriesConnection(number.circuitConnection()).seriesConnection(a.parallelConnection(dot.parallelConnection(dot.seriesConnection(number.circuitConnection()))))
    Number.fomalize()
    Number.showTransferTable()
    # test5 = a.seriesConnection(b).circuitConnection().seriesConnection(a.circuitConnection().parallelConnection(b.circuitConnection())).seriesConnection(b.seriesConnection(a).circuitConnection())
    # drawNFA(test5)
    # test5.fomalize()
    # test5.showTransferTable()
    # DFAtest = DFA(test5)
    DFAtest = DFA(Number)
    DFAtest.showTransferTable()
    print DFAtest.trans('a', 0)
    DFAtest.draw()
    print DFAtest.endStates
